package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/8/14 22:24
 */
public class LongestPalindromeSubseq_516 {

    public int longestPalindromeSubseq(String s) {
        final char[] chars = s.toCharArray();
        final int len = chars.length;
        final int[][] dp = new int[len][len];

        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }

        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j < i; j++) {
                if (chars[i] == chars[j])
                    // 注意这里是加2
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    // 否则应该取两边的最大值
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }

        // 取的是从0~5的长度
        return dp[0][len - 1];
    }

    static class Solution {
        public int longestPalindromeSubseq(String s) {
            int len = s.length();
            if (len == 0) return 0;

            int[][] dp = new int[len][len];

            for (int i = 0; i < len; i++) {
                // 字符相等时为1
                dp[i][i] = 1;
            }

            for (int i = len - 2; i >= 1; i--) {
                for (int j = i + 1; j < len; j++) {
                    if (s.charAt(i) == s.charAt(j)) {
                        // 左右相等，那么在原来的基础上加2
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else {
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                    }
                }
            }

            return dp[len - 1][len - 1];
        }
    }

}
